Complexité de temps — Suite

Ce document couvre les complexités avancées qui apparaissent dans les algorithmes de tri et les problèmes combinatoires.

Analogie : Le sac de billes

Imagine un sac contenant n billes numérotées.

Complexité	Scénario avec le sac de billes
O(1)	Tu piges une seule bille et tu t'arrêtes. Toujours 1 action, peu importe combien il y a de billes dans le sac.
O(log n)	Les billes sont déjà alignées en ordre sur une table. Tu cherches la n°47 : tu regardes celle du milieu — trop haute, tu ignores toute la droite. Tu recommences sur la moitié restante. À chaque étape tu coupes le problème en deux → log n étapes suffisent.
O(n)	Tu piges les billes une par une sans les remettre jusqu'à trouver la bonne. Dans le pire cas (c'est la dernière), tu fais n tirages.
O(n log n)	Tu as 100 billes dont 50 sont déjà alignées en ordre sur la table. Tu piges une bille du sac et, grâce à la rangée triée, tu coupes en deux à chaque fois pour trouver sa place exacte (log n coups). Tu fais ça pour chacune des 50 billes restantes → n billes × log n comparaisons chacune.
O(n²)	Tu as 200 billes numérotées de 1 à 100, chaque numéro en double. Tu piges une bille, puis tu fouilles le sac une par une pour trouver sa jumelle (n coups). Tu recommences pour chaque bille → n billes × n coups chacune = n² tirages au total.
O(2ⁿ)	Tu as n billes et un sac vide. Pour chaque bille, tu décides : dedans ou pas. Avec 2 billes : {} {1} {2} {1,2} → 4 sacs. Ajoute la bille 3 : chacun des 4 sacs se dédouble (avec ou sans la 3) → 8 sacs. Chaque bille ajoutée double le total → 2ⁿ combinaisons.
O(n!)	Tu vides le sac en pigeant une bille à la fois sans la remettre — le nombre de séquences différentes possibles est n! (ex. 3 billes → 6 séquences, 5 billes → 120 séquences).

Retenir : plus la complexité est élevée, plus ajouter une seule bille au sac explose le nombre d'opérations nécessaires.

Complexités avancées

5. O(n log n) – Linéaire logarithmique

C'est la complexité des bons algorithmes de tri.

Exemple avec les billes : Tu as 8 billes à ranger en ordre sur une table. Tu en piges une, et pour trouver où la placer, tu coupes la rangée existante en deux à chaque fois plutot que de comparer une à une — en 3 comparaisons maximum tu sais où elle va (log₂8 = 3). Tu fais ça pour chacune des 8 billes → 8 × 3 = 24 opérations.

Si tu avais 1 000 billes : 1 000 × 10 = 10 000 opérations (au lieu de 1 000 000 avec O(n²)).

Pourquoi O(n log n) ?

• n : on traite chaque élément une fois.
• log n : pour chaque élément, on fait log n comparaisons (en coupant en deux à chaque étape).
• Total = n × log n.

6. O(2ⁿ) – Exponentielle

Chaque élément ajouté double le nombre d'opérations.

Exemple avec les billes : Tu as n billes et tu veux lister toutes les sélections possibles d'un sac vide. Pour chaque bille, tu décides : dedans ou pas.

• 1 bille → {} {1} → 2 sacs
• 2 billes → {} {1} {2} {1,2} → 4 sacs
• 3 billes → {} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} → 8 sacs

Chaque nouvelle bille dédouble tous les sacs existants (une version sans elle, une avec). Tu ajoutes une 4ème bille ? Les 8 sacs deviennent 16. Une 5ème ? 32. À 30 billes, tu dépasses un milliard de combinaisons.

Pourquoi O(2ⁿ) ?

• Chaque élément a 2 états : inclus ou exclu.
• n = 10 → 1 024 combinaisons.
• n = 30 → 1 073 741 824 combinaisons !

7. O(n!) – Factorielle

Le pire des cas : le nombre de permutations possibles d'un ensemble.

Exemple concret : Génération de toutes les permutations

On retire une bille du sac, puis une autre, puis une autre… sans jamais les remettre. L'ordre dans lequel on les pige forme une séquence unique.

Pourquoi O(n!) ?

• Si on a 3 éléments → 3! = 6 permutations.
• Si on a 5 éléments → 5! = 120 permutations.
• Avec 10 éléments ? 10! = 3 628 800 combinaisons — inexploitable pour n > 12.

Récapitulatif complet

Notation	Nom	Exemple	Taille max réaliste (n)
O(1)	Constant	Accès à un tableau	∞
O(log n)	Logarithmique	Recherche binaire	1 milliard
O(n)	Linéaire	Parcourir une liste	10-100 millions
O(n log n)	Linéaire logarithmique	Tri fusion	1-10 millions
O(n²)	Quadratique	Tri par sélection	~10,000
O(2ⁿ)	Exponentielle	Fibonacci naïf	~30
O(n!)	Factorielle	Voyageur de commerce	~10

Règles importantes

1. On ignore les constantes

   • O(2n) → O(n)
   • O(5 log n) → O(log n)

2. On garde le terme dominant

   • O(n + n²) → O(n²)
   • O(n log n + n) → O(n log n)

3. On ne compte que le pire cas (worst-case)

   • Un tri rapide peut être O(n log n) en général mais O(n²) dans le pire cas.

Conclusion

• Toujours viser les complexités les plus faibles possible.
• O(log n) et O(n log n) sont optimaux pour beaucoup de problèmes.
• O(n²) et pire sont à éviter pour de grandes valeurs de n.